The present invention relates to a high speed, relatively low cost search processor for rapidly and efficiently searching an ordered linked list of data items on the basis of a search argument which is representative of the magnitude of a new data entry to be selectively inserted into a linked list. The new linked list search processor has particular application to a real time, computer grahics system or to a higher performance, special purpose computer generated imagery system adapted to produce realistic pictures of three dimensional objects on a video display. Briefly, and in general terms, computer graphics systems are presently known which are able to process full color perspective views of objects and scenes by incorporating therein a hidden surface algorithm with variable intensity shading, so that a realistic image or scene may be accurately portrayed. Such computer graphics systems are capable of several different applications including, but not limited to, flight simulation techniques, computer aided design, architectural planning, and mathematical modeling.
However, computer generated imagery systems of the prior art in which real time performance capabilities are incorporated (i.e. those which are adapted to generate at least 30 picture frames per second) generally include an array of hardware components and microelectronic devices which are arranged to form a system that has proven both costly to implement and relatively difficult to use. Moreover, the enormous computation rate that is needed to generate video data at a rate approaching real time also frequently requires a multitude of relatively expensive, high speed hardware components.
As will be known to those skilled in the art, conventional computer generated imagery or graphics systems are capable of displaying pictures of three dimensional objects, which objects are typically defined by a plurality of mathematical elements, such as polygons, surface patches, and other higher order surfaces. That is, stored computer data is used to generate an array of scan lines, with a particular array of such scan lines defining a polygon, or the like. More particularly, each scan line has a length of several pixels which, when displayed, may represent part of one or more polygons. The alignment of pluralities of successive scan lines forms a picture to be displayed.
Data, which is representative of a compilation of information regarding segments which form a respective scan line and, accordingly, portions of one or more respective polygons, is stored in the form of an ordered or linked list in a computer memory. Such data items of the linked list include the length and starting coordinate of each scan line segment as well as a pointer to direct a processor unit to the next successive entry in the list. According to conventional techniques, the information content of the linked list is searched sequentially via a path that is mapped out by the pointers of successive data items, so that, eventually, a new data entry containing information regarding a scan line segment can be properly added to and combined with existing data items of the list in such a prescribed order so as to form a complete scan line when the data is assembled and displayed. In other words, when each new data entry containing information regarding a scan line segment is read, a processing unit sequentially searches through the linked list of data items to determine the precise location for the new scan line segment, depending upon the magnitude of the starting coordinate thereof relative to the magnitudes of the starting coordinates of all other data items in the list.
As will be known to those skilled in the art, the sequential scanning of the data items in a linked list increases the processing time and the throughput delay before a scan line can be assembled and ultimately displayed. Consequently, when the linked list is particularly long or when the number of scan lines is relatively large, the inherent time delay in such a prior art system is undesirably maximized. Moreover, the processing equipment for performing the sequential scan of a linked list is undesirably complex and further contributes to the overall high cost of conventional computer graphics and computer generated imagery systems.
By way of example, one prior art technique for locating and identifying one of a plurality of stored data items on the basis of complex searching conditions (e.g. including equality, magnitude, and the like) is a content-addressable memory used in a parallel processor. Such a memory is conceptually described in the book CONTENT-ADDRESSABLE MEMORIES by Teuvo Kohonen, Springer-Verlag, ed., 1980, Section 3.4.5, pp. 158-161.
International patent application No. PCT/US81/233 describes a vector memory means and means for positioning line segments in a graphics display system according to the starting coordinate values of the segments.
Some other documents which describe a computer graphics system having means for arranging and displaying video data are identified below:
______________________________________ U.S. Pat. No. Issue Date ______________________________________ 3,925,776 December 9, 1975 3,944,997 March 16, 1976 4,233,601 November 11, 1980 4,241,341 December 23, 1980 4,364,037 December 14, 1982 ______________________________________